﻿//402.移掉k位数字
//给你一个以字符串表示的非负整数 num 和一个整数 k 
//移除这个数中的 k 位数字，使得剩下的数字最小。请你以字符串形式返回这个最小的数字。
class Solution {
public:
    string removeKdigits(string num, int k)
    {
        string ret;
        int numk = 0;
        if (num.empty())
        {
            return ret;
        }
        stack<char> sta;
        for (int i = 0; i < num.size(); i++)
        {
            if (sta.empty() || sta.top() <= num[i] || numk >= k)
            {
                sta.push(num[i]);
            }
            else if (numk < k)
            {
                while (numk < k && !sta.empty() && sta.top() > num[i])
                {
                    sta.pop();
                    numk++;
                }
                sta.push(num[i]);
            }
        }
        while (k - numk)
        {
            sta.pop();
            numk++;
        }
        while (!sta.empty())
        {
            ret.insert(ret.begin(), sta.top());
            sta.pop();
        }
        while (ret[0] == '0' && ret.size() != 1)
        {
            ret.erase(0, 1);
        }
        if (ret.empty())
        {
            ret += '0';
        }

        return ret;
    }
};